package primary.code05_Tree;

/**
 * leetcode https://leetcode.cn/problems/P
 * 搜索二叉树的后继节点，可以利用遍历节点值递增的特型，采用不同的方式
 *
 * @author Yudi Wang
 * @date 2021/7/12 18:50
 * <p>
 * 查找后继节点 (中序遍历的下一节点)
 * 分为两种情况
 * 1 有右树，后继节点为右子树的最左节点
 * 2 无右树，本节点作为 后继节点的左子树最右节点，也可能不存在
 */
public class Code09_NextNode {

    private static Nodep getNextNode(Nodep head, Nodep p) {
        if (head == null || p == null) return null;
        //无右子树
        if (p.right == null) {
            Nodep cur = p;
            Nodep par = cur.parent;
            while (par != null && par.left != cur) {
                cur = par;
                par = cur.parent;
            }
            return par;
        }
        //有右子树
        else {
            Nodep cur = p.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }
    }

    private static Nodep getNextNodeTest(Nodep head, Nodep p) {
        if (head == null || p == null) return null;
        if (p.right != null) {
            Nodep cur = p.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }
        Nodep child = p;
        Nodep cur = p.parent;
        while (cur != null && cur.left != child) {
            child = cur;
            cur = cur.parent;
        }
        return cur;
    }

    public static void main(String[] args) {
        Nodep head = new Nodep(4);
        head.parent = null;
        head.left = new Nodep(3);
        head.left.parent = head;
        head.right = new Nodep(8);
        head.right.parent = head;
        head.left.left = new Nodep(2);
        head.left.left.parent = head.left;
        head.left.right = new Nodep(4);
        head.left.right.parent = head.left;
        head.right.left = new Nodep(7);
        head.right.left.parent = head.right;
        head.right.right = new Nodep(9);
        head.right.right.parent = head.right;
        head.right.right.right = new Nodep(10);
        head.right.right.right.parent = head.right.right;
//        Nodep next = getNextNode(head, head.left.right);
//        Nodep next = getNextNode(head, head.right.right.right);
        Nodep next1 = getNextNode(head, head.right);
        Nodep next2 = getNextNodeTest(head, head.right);
        System.out.println(next1 != null ? next2.data : null);
        System.out.println(next1 != null ? next2.data : null);
    }
}
